//
//  ArithmeticViewController.m
//  Common
//
//  Created by fangyuan ding on 2021/11/3.
//

#import "ArithmeticViewController.h"

#include <assert.h>

#define N 5
@interface ArithmeticViewController ()

@end

@implementation ArithmeticViewController

- (void)viewDidLoad {
    [super viewDidLoad];
//    int a[10]={34,18,23,56,39,15,89,14,48,24};
//    selectSort(a,10);
  
//    int a[10] = {};
//    a[0] = 1;
//    a[1] = 1;
//    for(int i = 2; i < 10; i++){
//        if(i %2 == 1){
//            a[i] = a[i-1] + a[i - 2];
//
//        }else if(i % 2 == 0){
//            a[i] = 2 *(a[i-1] + a[i-2]);
//        }
//    }
    
//    for(int i = 1; i < 10; i++){
//        printf("======%d=====\n",func(i));
//    }
//    printf("\n");
//    第二题：
//    给定一个int型数组，找出其中大于0的数字中倒数第二小的数字的下标
//    例如 1 -1 3 2 0，其中大于0的数字有1 3 2，倒数第二小的数字为2，其下标为3
//    尽量不使用排序
    int a[10]={34,18,23,56,39,15,89,14,48,24};
    find_sec_max(a,10);
}
//第一题：
//数列前2项为 1 1，从第3项开始，若为奇数项，则值为前两项之和，若为偶数项，则值为前两项之和的2倍
//可知该数列前6项为 1 1 2 6 8 28
//求该数列的第n项
int func(int n){
    if(n == 1 || n == 2){
        return 1;
    }else if(n % 2 == 0){
        return (func(n-1) + func(n-2)) * 2;
    }else if(n % 2 == 1){
        return  func(n-1) + func(n - 2);
    }
    return 0;
}



int find_sec_min(int data[],int n)
{
    int first_min,sec_min,i;
    if (n<2)
    {
 
        assert(n>=2);
    }
    if (data[0]>data[1])
    {
        first_min=data[1];
        sec_min=data[0];
    }
    else
    {
        first_min=data[0];
        sec_min=data[1];
    }
    for ( i=2;i<n;i++)
    {
        if (data[i]<first_min)
        {
            sec_min=first_min;
            first_min=data[i];
        }
        else
        {
            if (data[i]<sec_min)
            {
                sec_min=data[i];
            }
        }
    }
    for (i=0;i<n;i++)
    {
        if (data[i]==sec_min)
        {
             break;
        }
    }
    printf("=====%d==\n",sec_min);
    return sec_min;
}
//第二题：
//给定一个int型数组，找出其中大于0的数字中倒数第二小的数字的下标
//例如 1 -1 3 2 0，其中大于0的数字有1 3 2，倒数第二小的数字为2，其下标为3
//尽量不使用排序
int find_sec_max(int data[],int n)
{
    int first_max,sec_max,i;
    if (n<2)
    {
 
        assert(n>=2);
    }
    if (data[0]>data[1])
    {
        sec_max=data[1];
        first_max=data[0];
    }
    else
    {
        sec_max=data[0];
        first_max=data[1];
    }
    for ( i=2;i<n;i++)
    {
        if (data[i] > first_max)
        {
            sec_max = first_max;
            first_max=data[i];
        }
        else
        {
            if (data[i] > sec_max)
            {
                sec_max=data[i];
            }
        }
    }
    for (i=0;i<n;i++)
    {
        if (data[i]==sec_max)
        {
             break;
        }
    }
    printf("=====%d==\n",sec_max);
    return sec_max;
}
//选择排序
void selectSort(int *arr, int length) {
    for (int i = 0; i < length - 1; i++) { //趟数
        for (int j = i + 1; j < length; j++) { //比较次数
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
 
}
//冒泡排序
void bublleSort(int *arr, int length) {
    for(int i = 0; i < length - 1; i++) { //趟数
        for(int j = 0; j < length - i - 1; j++) { //比较次数
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
// 已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置，二分算法
int findKey(int *arr, int length, int key) {
    int min = 0, max = length - 1, mid;
    while (min <= max) {
        mid = (min + max) / 2; //计算中间值
        if (key > arr[mid]) {
            min = mid + 1;
        } else if (key < arr[mid]) {
            max = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
@end
